The present invention is directed to the area of software testing, in particular the testing of implementations of specifications therefor, where the specifications are expressed as multiple-model state-rich architectures. Specifications particularly suitable for modeling are software applications and physical systems running from alarm clocks to automatic teller machines to complex systems such as aircraft.
The use of finite state machines (FSMs) and extended finite state machines (EFSMs) for modeling real-life problems is known, as reflected in The STATEMATE Approach to Complex Systems, by i-Logix of Burlington, Massachusetts (1990); and D. Harel et al., STATEMATE: A Working Environment for the Development of Complex Reactive Systems, IEEE Transactions on Software Engineering, Vol. 16, No. (Apr. 1990). See also W. H. Jessop et al., Atlas--An Automated Software Testing System, Bell Laboratories, Inc., 13th IEEE Computer Society International Conference, pp. 337-340 (1976) and 2nd International Conference on Software Engineering, pp. 629-635 (1976). Various test selection methods for systems expressed as finite state machines are discussed in S. Fujiwara et al., Test Selection Based on Finite State Models, IEEE Transactions on Software Engineering, Vol, 17, No. 6 (Jun. 1991) and W. H. Jessop et al.
EFSMs are also discussed at length in applicant's copending patent applications, as follows:
"Method and Apparatus for Testing Implementations of Software Specifications" (the "ISL Testing" application) Ser. No. 08/100,006, filed Jul. 29, 1993 , PA1 "Method and Apparatus for Transforming a Specification into an Extended Finite State Machine" (the "ISL Transformation" application) Ser. No. 08/100,005, filed Jul. 29, 1993; PA1 "Method and Apparatus for Schematic Routing" (the "STE Routing"application) Ser. No. 08/100,001, filed Jul. 29, 1993; and PA1 "Method and Apparatus for Schematic Panning" (the "STE Panning" application) Ser. No. 08/100,007, filed Jul. 29, 1993.
Each of the foregoing patent applications was filed with the United States Patent Office on Jul. 29, 1993, along with the present application, and each of the applications and articles cited above is incorporated herein by reference.
The Atlas system is described as modeling, for instance, part of a telephone switching system, and a coverage scheme is used to traverse the model, thereby deriving tests for the switching system. However, the Atlas system is directed to only a single model; that is, there is no provision for a second model to be called by the first model, in effect creating a submodel, nor for a model to recursively call itself. Only nonhierarchical flow is possible using a system like Atlas, and thus the systems which may be exhaustively modeled are limited. Traversal of a model (i.e. generating test paths through the model) can be carried out only at one level.
In addition, although the Atlas system outputs a graphical representation of the model, this representation is "dead"; i.e., it cannot be used to input or edit the model.
The STATEMATE system also uses connected graphs to represent models, but tests only the specification itself, and not the implementation of the modeled system.
No prior system known to applicant is capable of modeling the specification of a state-rich structure as an EFSM with multiple levels of models, and of generating tests of the EFSM against a specification to ensure that a planned implementation complies with the specification. Such a system is needed in the case of complex structures, which in the past have been traversed only as simplified, single-level (or "flat") models.